package com.hy.hash;

import java.util.ArrayList;
import java.util.List;

public class CommonChars {

    /**
     * 1002. 查找常用字符
     *
     * 给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
     *
     * 示例 1：
     * 输入：words = ["bella","label","roller"] 输出：["e","l","l"] 示例 2：
     *
     * 输入：words = ["cool","lock","cook"] 输出：["c","o"]
     *
     * 提示：
     * 1 <= words.length <= 100 1 <= words[i].length <= 100 words[i] 由小写英文字母组成
     *
     * 思路
     * 这道题意一起就有点绕，不是那么容易懂，其实就是26个小写字符中有字符 在所有字符串里都出现的话，就输出，重复的也算。
     *
     * 例如：
     * 输入：["ll","ll","ll"] 输出：["l","l"]
     * 这道题目一眼看上去，就是用哈希法，“小写字符”，“出现频率”， 这些关键字都是为哈希法量身定做的啊
     *
     * @param a
     */

    public static List<String> commonChars(String [] a){
        List<String> res = new ArrayList<>();
        if (a.length == 0){
            return res;
        }
        // 用来统计所有字符串里字符出现的最小频率
        int [] hash = new int[26];
        // 用第一个字符串给hash初始化  获取第一个字符串  字母出现的频率
        for (int i = 0; i < a[0].length(); i++) {
            hash[a[0].charAt(i) - 'a'] ++;
        }
        // 统计除第一个字符串外字符的出现频率
        for (int i = 0; i < a.length; i++) {
            int [] hashOtherStr = new int[26];
            for (int j = 0; j < a[i].length(); j++) {
                hashOtherStr[a[i].charAt(j) - 'a'] ++;
            }
            // 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
            for (int k = 0; k < 26; k++) {
                //
                hash[k] = Math.min(hash[k],hashOtherStr[k]);
            }
        }
        // 将hash统计的字符次数，转成输出形式
        // 将hash统计的字符次数，转成输出形式
        for (int i = 0; i < 26; i++) {
            // 注意这里是while，多个重复的字符
            while (hash[i] != 0) {
                char c= (char) (i+'a');
                res.add(String.valueOf(c));
                hash[i]--;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        String[] words = {"bella","label","roller"};
        System.out.println(commonChars(words));


    }
}
